On the power domination number of de Bruijn and Kautz digraphs

摘要

Let $G=(V,A)$ be a directed graph without parallel arcs, and let $S\subseteqV$ be a set of vertices. Let the sequence $S=S_0\subseteq S_1\subseteqS_2\subseteq\cdots$ be defined as follows: $S_1$ is obtained from $S_0$ byadding all out-neighbors of vertices in $S_0$. For $k\geqslant 2$, $S_k$ isobtained from $S_{k-1}$ by adding all vertices $w$ such that for some vertex$v\in S_{k-1}$, $w$ is the unique out-neighbor of $v$ in $V\setminus S_{k-1}$.We set $M(S)=S_0\cup S_1\cup\cdots$, and call $S$ a \emph{power dominating set}for $G$ if $M(S)=V(G)$. The minimum cardinality of such a set is called the\emph{power domination number} of $G$. In this paper, we determine the powerdomination numbers of de Bruijn and Kautz digraphs.